package letcode2563

import "sort"

/*
*
2563. 统计公平数对的数目
题目地址https://leetcode.cn/problems/count-the-number-of-fair-pairs/description/
*
*/
func CountFairPairs(nums []int, lower int, upper int) int64 {
	sort.Ints(nums)
	var cn int
	for key, value := range nums {
		r := findPos(nums[:key], upper-value+1)
		l := findPos(nums[:key], lower-value)
		cn += r - l
	}
	return int64(cn)
}
func findPos(nums []int, target int) int {
	left, right := 0, len(nums) //左闭右开区间[left,right)
	for left < right {          //区间不为空
		// mid:=left+(right-left)>>1
		mid := (left + right) >> 1
		if nums[mid] < target {
			left = mid + 1 //[mid+1,right)
		} else {
			right = mid //[left,mid)
		}
	}
	return left //right
}
